package leetcode;

import util.TreeNode;

/**
 * @Project : AlgorithmLearning
 * @Package : Leetcode
 * @File : Q0106.java
 * @Author : WangRuoyu
 * @Date 2023/11/11 22:12
 */


public class Q0106 {
    private TreeNode createTree(int[] postorder, int[] inorder, int l1, int r1, int l2, int r2) {
        if (l1 > r1) return null;
        TreeNode node = new TreeNode(postorder[r1]);
        if (l1 == r1) return node;
        int k = l2;
        for (; k < r2; k++) {
            if (node.val == inorder[k]) break;
        }
        node.left = createTree(postorder, inorder, l1, l1 + k - l2 - 1, l2, k - 1);
        node.right = createTree(postorder, inorder, l1 + k - l2, r1 - 1, k + 1, r2);
        return node;
    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return createTree(postorder, inorder, 0, inorder.length - 1, 0, inorder.length - 1);
    }

    public static void main(String[] args) {
        Q0106 sl = new Q0106();
        int[] inorder = {9, 3, 15, 20, 7};
        int[] postorder = {9, 15, 7, 20, 3};
        TreeNode root = sl.buildTree(inorder, postorder);
    }
}